#include <kstdio.h>
#include <BuddyAllocator.h>

/*
 * Стратегия инициализации менеджера следующая:
 * 1. Заполняется список участков максимального размера т.е. 2^FRM_MAX_ORDER.
 * 2. Затем в данном списке просматриваются все участки памяти на предмет 
 *    нахождения в них зарезервированных фреймов.
 * 3. Если находится участок, в котором есть зарезервированные фреймы, он 
 *    разбивается на меньшие, пока не останутся участки с только свободными фреймами.
 * 4. В итоге приходим к состоянию, в котором все зарезервированные кадры могут находится
 *    только в списе единичных кадров. Проходим по этому списку и выкидываем все зарезервированные кадры.
 * 5. Если в дальнейшем, участок, по каким либо причинам перестанет быть 
 *    зарезервированным, он может быть без труда возвращен в распоряжение менеджера.
 */
BuddyFrameManager::BuddyFrameManager(Frame *first_frame_addr, uint32 sz){
	_frame_map		= first_frame_addr;
	_first_frn		= (mem_map - _frame_map) >> 12;
	_zone_size		= sz;
	_free_frames	= 0;
	/*
	 * Разбиваем область подконтрольную менеджеру на участки по 4 Мб.
	 */
	uint32 i = 0, step = 1UL << FRM_MAX_ORDER;
	Frame *fr;
	for(i = 0; i * step < _zone_size; i++){
		fr = (_frame_map + (i * step));
		(_frame_map + (i * step))->_order = FRM_MAX_ORDER;
		_frm_lists[FRM_MAX_ORDER].insEnd(&(_frame_map + (i * step))->_frames);
		_free_frames += step;
	}
	/*
	 * Проверяем 4Мб участки на наличие зарезервированных фреймов
	 */
	Frame	*cur_frm;
	Link	*lnk;
	int8	cur_order	= FRM_MAX_ORDER;
	bool	gonext		= true;
	while(cur_order > 0){
		step = 1UL << cur_order;
		lnk = _frm_lists[cur_order].getHead()->next;
		while(lnk != _frm_lists[cur_order].getHead()){
			cur_frm = get_obj(lnk, Frame, _frames);
			for(i = 0; i < step; i++){
				/*
				 * Если в блоке встречается зарезервированный фрейм, 
				 * то данный блок делим на два блока меньшей степени, 
				 * и переходим к следующему блоку.
				 */
				//kprintf("step: %i %i\n", step, i);
				if(cur_frm[i].isReserved()){
					lnk = _frm_lists[cur_order].remove(lnk);
					gonext = false;
					cur_frm->_order = --cur_order;
					(cur_frm + (1UL << cur_order))->_order = cur_order;
					_frm_lists[cur_order].insBegin(&cur_frm->_frames);
					_frm_lists[cur_order].insBegin(&(cur_frm + (1UL << cur_order))->_frames);
					cur_order++;
					break;
				}
			}
			if(gonext)
			lnk = lnk->next;
			gonext = true;
		}
		--cur_order;
	}
	
	/*
	 * Проверяем список единичных кадров на наличие зарезервированных, если они находятся, то выкидываем их.
	 */
	lnk = _frm_lists[0].getHead()->next;
	while(lnk != _frm_lists[0].getHead()){
		cur_frm = get_obj(lnk, Frame, _frames);
		if(cur_frm->isReserved()){
			lnk = _frm_lists[0].remove(lnk);
			--_free_frames;
		}else{
			lnk = lnk->next;
		}
	}
}

void BuddyFrameManager::printManager(){
	int i;
	for(i = 0; i <= FRM_MAX_ORDER; i++){
		kprintf("%i ", _frm_lists[i].getSize());
	}
	kprintf("\n");
}

/*
 * Выделение блока кадров
 * в качестве параметров передается массив флагов и размер выделяемого блока, 
 * выраженный двоичным логарифмом от размера выделяемого блока.
 */

Frame * BuddyFrameManager::_allocFrames(uint32 flags, uint32 order){
	uint32 cur_order = order;
	Frame *block, *buddy;
	Link *lnk;
	for(;cur_order <= FRM_MAX_ORDER; ++cur_order){
		if(!_frm_lists[cur_order].isEmpty()){
			while(cur_order > order){
				lnk = _frm_lists[cur_order].pop();
				block = get_obj(lnk, Frame, _frames);
				buddy = block + (1UL << (--cur_order));
				block->setOrder(cur_order);
				buddy->setOrder(cur_order);
				_frm_lists[cur_order].push(&buddy->_frames);
				_frm_lists[cur_order].push(&block->_frames);
			}
			lnk = _frm_lists[cur_order].pop();
			block = get_obj(lnk, Frame, _frames);
			block->setInUse();
			_free_frames -= 1UL << order;
			return block;
		}
	}
	kprintf("BUDDY_ERROR: Not enof memory!\n");
	return NULL;
}

/*
 * Выделение блока кадров состоящего из одного кадра
 */
/*
inline Frame * BuddyFrameManager::_allocFrame(uint32 flags){
	return _allocFrames(flags, 0);
}
*/

/*
 * Тоже что и allocFrame, но возвращает не адрес дескриптора фрейма, а адрес выделенного блока
 */
/*
inline void * BuddyFrameManager::allocFrames(uint32 flags, uint32 order){
	Frame *frm = _allocFrames(flags, order);
	return (void *)((frm - mem_map) << PAGE_SHIFT);
}
*/
/*
inline void * BuddyFrameManager::allocFrame(uint32 flags){
	return allocFrames(flags, 0);
}
*/

//Находит близнеца данного участка
#define get_buddy(frm, ord) \
	((((frm) - _frame_map) ^ (1 << (ord))) + _frame_map)

#define max(a, b) \
	(((a) > (b)) ? (a) : (b))
	
#define min(a, b) \
	(((a) < (b)) ? (a) : (b))
/*
 * Освобождает участок фреймов и пытается объеденить данный участок с близнецами
 * пока таковые находятся
 */
void BuddyFrameManager::freeFrames(Frame *startFrame){
	uint32 order = startFrame->_order;
	uint32 size_order = order;
	Frame *buddy, *tmp;
	while(order < 10){
		buddy = get_buddy(startFrame, order);
		if(!buddy->isReserved() && buddy->getOrder() == order && buddy->isFree()){
			
			_frm_lists[order].remove(&buddy->_frames);
			tmp = max(buddy, startFrame);
			startFrame = min(buddy, startFrame);
			buddy = tmp;
			buddy->setOrder(0);
			startFrame->setOrder(++order);
		}else{
			break;
		}
	}
	startFrame->clrInUse();
	_frm_lists[order].push(&startFrame->_frames);
	_free_frames += 1UL << size_order;
}

uint32 BuddyFrameManager::getFreeFrames(){
	return _free_frames;
}

void * BuddyFrameManager::operator new(size_t sz, void *addr){
	return addr;
}

